package com.zp.self.module.level_4_算法练习.算法.双指针.快慢指针;

import com.zp.self.module.level_4_算法练习.数据结构.链表.ListNode;

/**
 * @author By ZengPeng
 */
public class 力扣_61_旋转链表 {
    //测试
    public static void main(String[] args) {
        ListNode node = ListNode.getNode();
        ListNode listNode=null;

//        listNode= new 力扣_61_旋转链表().rotateRight(node,2);
        while (listNode!=null){
            System.out.print(listNode.val+",");
            listNode = listNode.next;
        }
        System.out.println();

        ListNode n1 = new ListNode(0);
        ListNode n2 = new ListNode(1);
        ListNode n3 = new ListNode(2);
        n1.next=n2;
        n2.next=n3;

        listNode = new 力扣_61_旋转链表().rotateRight(n3, 3);
        while (listNode!=null){
            System.out.print(listNode.val+",");
            listNode = listNode.next;
        }
    }

    /**
    题目：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

     示例 1：
     输入：head = [1,2,3,4,5], k = 2
     输出：[4,5,1,2,3]

     示例 2：
     输入：head = [0,1,2], k = 4
     输出：[2,0,1]

    分析：【perfect】
       1.先走一边记住长度len，并将链表合并成环，防止断节
           k % 长度len ,得到真正的位移量n，长度 -n = index [要返回的下标]
           执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    边界值 & 注意点：
       1.只有零个、一个、两个节点
     **/
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null) return null;
        ListNode quick = head;
        int len = 1;
        while (quick.next!=null){
            len++;
            quick = quick.next;
        }
        quick.next =head; //变成环
        int index = len-k%len;
        quick = head;
        while (index>1){
            quick = quick.next;
            index--;
        }
        head=quick.next;
        quick.next=null;
        return head;
    }
}
